package TSP;

import java.awt.Graphics2D;
import java.awt.geom.Line2D;

public class TSPMap 
{

	public City[] cityList;
	public int[] cityListIdSolver;
	public int nbCity;
	public boolean solved;
	public int debutPathId;
	public int currentCityDebugPathId;
	
	private int currentGreedyStepId;
	private int lastSolvedCityId;
	
	
	
	public TSPMap()
	{
		
	}
	
	public void Initialize(int nbCity)
	{
		this.nbCity = nbCity;
		cityList = new City[nbCity];
		cityListIdSolver = new int[nbCity];
	}

	public void AddCity(int cityId, float x, float y)
	{
		cityList[cityId] = new City(cityId, x, y, nbCity);
	}
	
	public void SetNeighbour()
	{
		int nbMaxNeighbour = Math.min(10, cityList.length - 1);
		
		for(int i = 0; i < nbCity; i++)
		{
			for(int j = 0; j < nbCity; j++)
			{
				if (i != j)
				{
					cityList[i].SetNeighbour(j, cityList[j]);
				}
			}
		}
	}
	
	public void CalculateNeighbourDistance()
	{
		for(int i = 0; i < nbCity; i++)
		{
			for(int j = i; j < nbCity; j++)
			{
				if (i != j)
				{
					double distance = (cityList[j].posX - cityList[i].posX)  * (cityList[j].posX - cityList[i].posX) + (cityList[j].posY - cityList[i].posY) * (cityList[j].posY - cityList[i].posY);
					distance = Math.sqrt(distance);
					cityList[i].distance[j] = distance;
					cityList[j].distance[i] = distance;
				}
			}
		}
	}
	
	public void Solve()
	{
		/*
		boolean didImprove = true;
		double bestDistance = 0;
		Route currentRoute = new Route();
		
		while(didImprove)
		{
			bestDistance = currentRoute.CalculateRouteDistance();
		}*/
		
		Greedy();
		//CrossCheck();
		//ThreeOpt();
		
		TwoOpt();
		CrossCheck();
		ThreeOpt();
		CrossCheck();
		//
		//CrossCheck();
		
		
		//TwoOpt();
		//double d2 = CalculateTotalDistance();

		
		/*
		   repeat until no improvement is made {
		       start_again:
		       best_distance = calculateTotalDistance(existing_route)
		       for (i = 0; i < number of nodes eligible to be swapped - 1; i++) {
		           for (k = i + 1; k < number of nodes eligible to be swapped; k++) {
		               new_route = 2optSwap(existing_route, i, k)
		               new_distance = calculateTotalDistance(new_route)
		               if (new_distance < best_distance) {
		                   existing_route = new_route
		                   goto start_again
		               }
		           }
		       }
		   }
		   */
	}
	
	private void reversePartArray(int startIndex, int endIndex)
	{
		int half = startIndex + ((endIndex + 1) - startIndex) / 2;
		int endCount = endIndex;
		for (int startCount = startIndex; startCount < half; startCount++) {
		    int store = cityListIdSolver[startCount];
		    cityListIdSolver[startCount] = cityListIdSolver[endCount];
		    cityListIdSolver[endCount] = store;
		    endCount--;
		}
	}
	 private void CrossCheck() {
			for ( int i = 0; i < nbCity - 2; i++ )
			{
				for ( int j = i + 2; j < nbCity; j++ )
				{
					boolean o = false;
					
					int c4id = j + 1;
					if (j == nbCity - 1)
					{
						c4id = 0;
					}
					City c1 = cityList[cityListIdSolver[i]];
					City c2 = cityList[cityListIdSolver[i + 1]];
					
					City c3 = cityList[cityListIdSolver[j]];
					City c4 = cityList[cityListIdSolver[c4id]];
					
					if (DoLineSegmentsIntersect(c1.posX, c1.posY, c2.posX, c2.posY, c3.posX, c3.posY, c4.posX, c4.posY))
					{
						if (c4id == 0)
						{
							int bob = 0;
							bob++;
						}
						reversePartArray(i + 1, j);
						//int tmp = cityListIdSolver[i + 1];
						//cityListIdSolver[i + 1] = cityListIdSolver[j];
						//cityListIdSolver[i] = tmp;

					}
				
				}
			}
			for(int i = 0; i < nbCity - 1; i++)
			{
				cityList[cityListIdSolver[i]].setNextDestination(cityList[cityListIdSolver[i + 1]]);
			}
			
			cityList[cityListIdSolver[nbCity - 1]].setNextDestination(cityList[cityListIdSolver[0]]);
	}

	static boolean IsOnSegment(double xi, double yi, double xj, double yj,
                        double xk, double yk) {
  return (xi <= xk || xj <= xk) && (xk <= xi || xk <= xj) &&
         (yi <= yk || yj <= yk) && (yk <= yi || yk <= yj);
}

static int ComputeDirection(double xi, double yi, double xj, double yj,
                             double xk, double yk) {
  double a = (xk - xi) * (yj - yi);
  double b = (xj - xi) * (yk - yi);
  return a < b ? -1 : a > b ? 1 : 0;
}

// Do line segments (x1, y1)--(x2, y2) and (x3, y3)--(x4, y4) intersect? 
boolean DoLineSegmentsIntersect(double x1, double y1, double x2, double y2,
                             double x3, double y3, double x4, double y4) {
	int d1 = ComputeDirection(x3, y3, x4, y4, x1, y1);
	int d2 = ComputeDirection(x3, y3, x4, y4, x2, y2);
	int d3 = ComputeDirection(x1, y1, x2, y2, x3, y3);
	int d4 = ComputeDirection(x1, y1, x2, y2, x4, y4);
  return (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&
          ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) ||
         (d1 == 0 && IsOnSegment(x3, y3, x4, y4, x1, y1)) ||
         (d2 == 0 && IsOnSegment(x3, y3, x4, y4, x2, y2)) ||
         (d3 == 0 && IsOnSegment(x1, y1, x2, y2, x3, y3)) ||
         (d4 == 0 && IsOnSegment(x1, y1, x2, y2, x4, y4));
}
	
	void ThreeOpt()
	{
		// Get tour size
		int size = nbCity;

		for ( int i = 0; i < size - 5; i++ )
		{
			for ( int j = i + 2; j < size - 3; j++ )
			{
				for ( int k = j + 2; k < size - 1; k++ )
				{
					int c1 = i;
					int c2 = i + 1;
					int c3 = j;
					int c4 = j + 1;
					int c5 = k;
					int c6 = k + 1;

					DoThreeOpt( c1, c2, c3, c4, c5, c6 );	
				}
			}	

		}
		
		for(int i = 0; i < nbCity - 1; i++)
		{
			cityList[cityListIdSolver[i]].setNextDestination(cityList[cityListIdSolver[i + 1]]);
		}
		
		cityList[cityListIdSolver[nbCity - 1]].setNextDestination(cityList[cityListIdSolver[0]]);
	}
	
	void TwoOpt()
	{
		// Get tour size
		//double size = CalculateTotalDistance();

		for ( int i = 0; i < nbCity - 2; i++ )
		{
			for ( int j = i + 2; j < nbCity; j++ )
			{
				boolean o = false;
				if (j == nbCity - 1)
				{
					o = true;
					j = 0;
				}
				int c1 = i;
				int c2 = i + 1;
				int c3 = j;
				int c4 = j + 1;

				DoTwoOpt( c1, c2, c3, c4 );		
				if (o)
				{
					j = nbCity;
				}
			}	
		}
		
		for(int i = 0; i < nbCity - 1; i++)
		{
			cityList[cityListIdSolver[i]].setNextDestination(cityList[cityListIdSolver[i + 1]]);
		}
		
		cityList[cityListIdSolver[nbCity - 1]].setNextDestination(cityList[cityListIdSolver[0]]);


	}
	

	private void DoTwoOpt(int c1, int c2, int c3, int c4) 
	{
		// Feasible exchanges only
		if ( c3 == c1 || c3 == c2 || c4 == c1 || c4 == c2 ) return;

		// Store original orderings
		int c1old = cityListIdSolver[c1];
		int c2old = cityListIdSolver[c2];
		int c3old = cityListIdSolver[c3];
		int c4old = cityListIdSolver[c4];

		double old_distance = CalculateTotalDistance();	
		
		// Leave values at positions c1, c4
		// Swap c2, c3 values
		// c3 -> c2
		// c2 -> c3
		int tmp = cityListIdSolver[c2];
		cityListIdSolver[c2] = cityListIdSolver[c3];
		cityListIdSolver[c3] = tmp;

		double new_distance = CalculateTotalDistance();	

		// Re-instate if not an immprovement
		if ( new_distance > old_distance )
		{
			cityListIdSolver[ c1 ] = c1old;
			cityListIdSolver[ c2 ] = c2old;
			cityListIdSolver[ c3 ] = c3old;
			cityListIdSolver[ c4 ] = c4old;
		}
		else
		{
			int breakMe = 0;
			breakMe++;
		}
	}

	
	private void DoThreeOpt(int c1, int c2, int c3, int c4, int c5, int c6) 

{
// Store original orderings
int c1old = cityListIdSolver[c1];
int c2old = cityListIdSolver[c2];
int c3old = cityListIdSolver[c3];
int c4old = cityListIdSolver[c4];
int c5old = cityListIdSolver[c5];
int c6old = cityListIdSolver[c6];

double old_distance =  CalculateTotalDistance();	


// Swap 1: 40526
// c2 -> c4	
// c4 -> c6
// c6 -> c2
int tmp1 = cityListIdSolver[c2];	
cityListIdSolver[ c2 ] = cityListIdSolver[c4];	
cityListIdSolver[ c4 ] = cityListIdSolver[c6];
cityListIdSolver[ c6 ] = tmp1;

double new_distance1 = CalculateTotalDistance();

// Re-instate if not an immprovement
if ( new_distance1 > old_distance )
{
	cityListIdSolver[ c1 ] = c1old;
	cityListIdSolver[ c2 ] = c2old;
cityListIdSolver[ c3 ] = c3old;
cityListIdSolver[ c4 ] = c4old;
cityListIdSolver[ c5 ] = c5old;
cityListIdSolver[ c6 ] = c6old;
}
else
{
c1old = cityListIdSolver[c1];
c2old = cityListIdSolver[c2];
c3old = cityListIdSolver[c3];
c4old = cityListIdSolver[c4];
c5old = cityListIdSolver[c5];
c6old = cityListIdSolver[c6];

old_distance = new_distance1;
}


// Swap 2: 
// c2 -> c4	
// c4 -> c5
// c5 -> c2
tmp1 = cityListIdSolver[c2];	
cityListIdSolver[ c2 ] = cityListIdSolver[c4];	
cityListIdSolver[ c4 ] = cityListIdSolver[c5];		
cityListIdSolver[ c5 ] = tmp1;

new_distance1 = CalculateTotalDistance();

// Re-instate if not an immprovement
if ( new_distance1 > old_distance )
{
	cityListIdSolver[ c1 ] = c1old;
	cityListIdSolver[ c2 ] = c2old;
	cityListIdSolver[ c3 ] = c3old;
	cityListIdSolver[ c4 ] = c4old;
	cityListIdSolver[ c5 ] = c5old;
	cityListIdSolver[ c6 ] = c6old;
}





}
	
	private double CalculateTotalDistance() 
	{
		/*
		int t = 0;
		double dist = 0;
		City c1 = cityList[0];
		City c2 = cityList[0];
		 
		 for(int i  = 0; i < nbCity; i++)
		 {
			 c1 = cityList[t];
			 c2 = cityList[t].getNextDestination();
			 dist += c1.distance[c2.originalId];
		     t = c2.originalId;
		 }
		 
		 dist += c2.distance[0];
		return dist;
		*/
		
		
		double dist = 0;
		City c1 = cityList[0];
		City c2 = cityList[0];
		 
		 for(int i  = 0; i < nbCity - 1; i++)
		 {
			 c1 = cityList[cityListIdSolver[i]];
			 c2 = cityList[cityListIdSolver[i + 1]];
			 dist += c1.distance[c2.originalId];
		 }
		 
		 dist += c2.distance[0];
		return dist;
	}

	private void Greedy() 
	{
		int cityId = 0;
		cityList[cityId].setUsed(true);
		
		
		while(cityId < cityList.length)
		{
			GreedyOneStep();
			cityId++;
		}
		
		cityList[lastSolvedCityId].setNextDestination(cityList[0]);
		
		cityListIdSolver[0] = 0;
		for(int i = 1; i < nbCity; i++)
		{
			cityListIdSolver[i] = cityList[cityListIdSolver[i - 1]].getNextDestination().originalId;
		}
		int b = 21;
	}
	
	public void GreedyStep()
	{
		if (currentGreedyStepId < cityList.length - 1)
		{
			GreedyOneStep();
		}
		
		currentGreedyStepId++;
		
		if (currentGreedyStepId == cityList.length)
		{
			cityList[lastSolvedCityId].setNextDestination(cityList[0]);
		}
		
		
	}

	private void GreedyOneStep() 
	{
		City city = cityList[0];
		
		/*if (lastSolvedCityId == 39)
		{
			city = cityList[49];
		}*/
		/*else if (lastSolvedCityId == 18)
		{
			city = cityList[11];
		}*/
		//else
		{
			city = cityList[lastSolvedCityId].FindNearestFreeNeighbour();
		}
		
		if (city != null)
		{
			city.setUsed(true);
			cityList[lastSolvedCityId].setNextDestination(city);
			lastSolvedCityId = city.originalId;
		}
	}
}